package edu.pw.elka.gtsna.graph_algorithms;


public class FindUnion {

	
	int parent [];
	int rank [];
	int size;
	
	
	public FindUnion(int size){
		parent = new int[size+1];
		rank = new int[size+1];
		this.size = 0;
	}
	
	
	public void add(int x){
		parent[x] = x;
		rank[x] = 0;
		size++;
	}
	
	public int find(int x){
		if (parent[x] == 0)
			return 0;
		
	    if (parent[x] != x){
	       parent[x] = find(parent[x]);
	    }
	    return parent[x];
	}
	
	public void merge(int x, int y){
		int rootx = find(x);
		int rooty = find(y);
		
		if (rootx == rooty)
			return;
		
		if (rootx == 0) {
			add(x);
			rootx = find(x);
		}
		
		if (rooty == 0) {
			add(y);
			rooty = find(y);
		}
		
		
		if (rank[rootx] < rank[rooty]){
			parent[rootx] = rooty;
		} else if (rank[rootx] > rank[rooty]) {
			parent[rooty] = rootx;
		} else {
			parent[rooty] = rootx;
			rank[rootx]++;
		}
		size--;
	}
	
	public int size(){
		return size;
	}
	
	public void clear(){
		for(int i=0; i<parent.length;i++){
			parent[i] = 0;
			rank[i] = 0;
		}
		size=0;
	}
	
}
